<?php
// Sort integer array consisting of 1, 2, 3
// Alog:
// 1. Keep stack position for the 3 and 1
// 2. Swap 3 with end of array and 1 with start of array, keep the 2s
// 3. Incrementing the stack positions
// 4. STOP loop when stack position of 3 is colliding with the search index

require_once 'util.php';

$values = generateRandomArray(1, 3, 20);

echo "Before:";
var_dump( $values );

dutch_sort( $values );

echo "After:";
var_dump( $values );

function dutch_sort( &$values ){
	$lenght = count( $values );

	if( 1 >= $lenght ){
		return;
	}

	// 1s from front
	$p = -1;
	// 3s from end
	$q = $lenght;

	// Important !!!
	// Traverse up, until cur pos meets pos of 3
	for( $index=0; $index<$q; ){
		if( $values[$index] > 2 ){
			// Go to the back!
			swap( $values, $index, --$q );
		}
		else if($values[$index] < 2){
			// Go to the front!
			swap( $values, $index, ++$p );
			$index++;
		}
		else {
			// Just stay
			$index++;
		}
	}

	return;
}